#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //动态规划，设dp[i]为到第i个数字为止的最长递增长度
        //设计O(n^2)的算法
        vector<int> dp(nums.size(),1);
        for(int i = 1;i<nums.size();++i){
            for(int j = i-1;j>=0;--j){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[j]+1,dp[i]);
                }
            }
        }
        int result = 0;
        for(int i = 0;i<dp.size();++i){
            result = max(result,dp[i]);
        }   
        return result;
    }
};

int main(){
    Solution S;
    vector<int> nums = {0,1,0,3,2,3};
    cout<<S.lengthOfLIS(nums)<<endl;
}